package search;
// 搜索二维矩阵
public class leetcode74 {
    public static void main(String[] args) {
        int[][] nums = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        int target = 16;
        printNums(nums);
        System.out.println(searchMatrix(nums, target));

    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        if(target < matrix[0][0] || target > matrix[matrix.length - 1][matrix[0].length - 1]){
            return false;
        }

        int left = 0;
        int right = matrix.length - 1;
        while (left <= right){
            int mid = (left + right)/2;

            if(target > matrix[mid][0]){
                left = mid + 1;
            }
            else if(target == matrix[mid][0]){
                return true;
            }
            else{
                right = mid - 1;
            }
        }

        int row = right;

        left = 0;
        right = matrix[0].length - 1;
        while (left <= right){
            int mid = (left + right)/2;

            if(target > matrix[row][mid]){
                left = mid + 1;
            }
            else if(target == matrix[row][mid]){
                return true;
            }
            else{
                right = mid - 1;
            }
        }

        return false;
    }

    public static void printNums(int[][] nums){
        for (int i = 0; i < nums.length; i++) {
            for(int j = 0; j < nums[0].length; j++){
                System.out.print(nums[i][j] + "\t");
            }
            System.out.println();
        }
    }
}
